package leetcode_500;

import java.util.Arrays;

/**
 *@author 周杨
 *Heaters_475 给定一些房子坐标 给定一些喇叭坐标 问喇叭的最小半径多少能影响到所有房子
 *describe:暴力解 每次找出房子最近的两个房子 AC 25%
 *2018年8月30日 下午2:46:48
 */
public class Heaters_475 {
	public int findRadius(int[] houses, int[] heaters) {
		   Arrays.sort(houses);
	       Arrays.sort(heaters);
	       int max=0;
	       for(int i=0;i<houses.length;i++)
	       {
	           //二分法找出第一个大于houses[i]的heater[mid]
	           int left=0;
	           int right=heaters.length-1;
	           while(left<right)//for循环是用来求解距离自己最近的heater
	           {
	               int mid=left+(right-left)/2;
	               if(houses[i]>heaters[mid])
	               {
	                   left=mid+1;
	               }
	               else
	                   right=mid;
	           }
	           if(right==0)//如果是第一个heater的话 距离就是用这个炉子减去房间的距离
	               max=Math.max(max,Math.abs(heaters[right]-houses[i]));
	          else {//其余的话，都是和上一个炉子和这个炉子减去房间的距离，选择其中最小的
	                   int distance1=Math.abs(heaters[right]-houses[i]);
	                   int distance2=Math.abs(houses[i]-heaters[right-1]);
	                   max=Math.max(max, Math.min(distance1, distance2));//在所有的距离里面选择最大值
	            }
	            
	       }
	       return max;
    }
}
